package com.kevin.algorithm;

import com.alibaba.fastjson.JSON;
import com.kevin.model.Location;
import com.kevin.utils.DistanceUtil;
import com.kevin.utils.MapUtils;
import com.kevin.utils.PointsRep;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

/**
 * @Description: 全排列算法，获取最短路径
 * 该算法指定了起止点
 *
 * @author kevin
 * @version V1.0
 * @date 2019/2/20 15:10
 **/
public class SortRoute implements AlgorithmStrategy{
    private static final Logger LOGGER = LoggerFactory.getLogger(ShortRoute.class);

    private List<Location> temp = null;
    private BigDecimal shortestDis = new BigDecimal(-1);
    private int sum = 0;

    private PointsRep pointsRep;

    @Override
    public Location[][] execute(PointsRep pointsRep) {
        LOGGER.info("全排列算法开始,入参：{}", JSON.toJSONString(pointsRep));

        this.pointsRep = pointsRep;

        List<Location> locations = this.pointsRep.getPoints();

        /**
         * 获取列表的全排列，计算出最短路径
         */
        perm(locations,0,locations.size()-1);

        Location[][] result = new Location[1][temp.size()];
        for(int i=0;i<temp.size();i++){
            result[0][i] = temp.get(i);
        }

        LOGGER.info("全排列算法结束，结果：{},计算次数为：{}",JSON.toJSONString(result),sum);

        /**
         * 获取全排列列表，获取最短路径
         */
        return result;
    }

    /**
     * 交换两个位置的信息
     *
     * @param locations
     * @param a
     * @param b
     */
    private void swap(List<Location> locations,int a,int b){
        Location temp = locations.get(a);
        locations.set(a,locations.get(b));
        locations.set(b,temp);
    }

    /**
     * 全排列list
     * @param locations
     * @param begin
     * @param end
     */
    private void perm(List<Location> locations,int begin,int end){
        if(begin == end){
            /**
             * 比对当前列表的路径距离
             */
            BigDecimal beginDis = BigDecimal.valueOf(Double.valueOf(DistanceUtil.algorithm(this.pointsRep.getBegin().getLon(),this.pointsRep.getBegin().getLat(),locations.get(0).getLon(),locations.get(0).getLat())));
            BigDecimal currDis = MapUtils.getListDis(locations);
            BigDecimal endDis = BigDecimal.valueOf(Double.valueOf(DistanceUtil.algorithm(this.pointsRep.getEnd().getLon(),this.pointsRep.getEnd().getLat(),locations.get(locations.size()-1).getLon(),locations.get(locations.size()-1).getLat())));
            currDis = beginDis.add(currDis).add(endDis);

            if(shortestDis.compareTo(new BigDecimal(-1)) == 0 || shortestDis.compareTo(currDis) == 1){
                shortestDis = currDis;
                List<Location> currList = new ArrayList<>();
                for(Location location : locations){
                    currList.add(location);
                }
                temp = currList;
            }

            //统计有多少排列
            sum++;

        }else{
            for(int j=begin;j<=end;j++){
                swap(locations,begin,j);
                perm(locations,begin+1,end);
                swap(locations,j,begin);
            }
        }
    }

}
